/*    Copyright 2010 Tobias Marschall
 *
 *    This file is part of MoSDi.
 *
 *    MoSDi is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    MoSDi is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with MoSDi.  If not, see <http://www.gnu.org/licenses/>.
 */

package mosdi.fa;

import mosdi.util.BitArray;

/** NFA that accepts a given string iff it is a suffix of
 *  the pattern p given at construction time. */
public class SuffixAutomaton extends NFA {

	private int alphabetSize;
	private int[] pattern;
	private BitArray[] transitionMasks;
	
	public SuffixAutomaton(int alphabetSize, int[] pattern) {
		this.alphabetSize = alphabetSize;
		this.pattern = pattern;
		transitionMasks = new BitArray[alphabetSize];
		for (int c=0; c<alphabetSize; ++c) {
			transitionMasks[c] = new BitArray(pattern.length+1);
		}
		for (int i=0; i<pattern.length; ++i) {
			transitionMasks[pattern[i]].set(i+1, true);
		}
	}

	@Override
	public int alphabetSize() {
		return alphabetSize;
	}

	@Override
	public BitArray acceptStates() {
		BitArray result = new BitArray(pattern.length + 1);
		result.set(pattern.length, true);
		return result;
	}

	@Override
	public BitArray startStates() {
		BitArray result = new BitArray(pattern.length + 1);
		result.invert();
		return result;
	}

	@Override
	public int stateCount() {
		return pattern.length + 1;
	}

	@Override
	public BitArray transition(BitArray activeStates, int character) {
		BitArray b = new BitArray(activeStates);
		b.shiftLeft();
		b.and(transitionMasks[character]);
		return b;
	}
	
	public boolean isSuffix(int[] string) {
		return accepts(string);
	}
	
	public boolean isFactor(int[] string) {
		return !read(string).allZero();
	}
	
	/** Returns true iff the transitions that leads from the (set of) start state(s)
	 *  to the given state set are a suffix of the underlying text. */
	public boolean isSuffix(BitArray states) {
		return states.get(pattern.length);
	}

	/** Returns true iff the transitions that leads from the (set of) start state(s)
	 *  to the given state set are a factor of the underlying text. */
	public boolean isFactor(BitArray states) {
		return !states.allZero();
	}

}
